﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
typedef int STDataType;
class Stack
{
public:
	Stack(int n = 4)
	{
		_a = (STDataType*)malloc(sizeof(STDataType) * n);
		if (nullptr == _a)
		{
			perror("malloc申请空间失败");
			return;
		}
		_capacity = n;
		_top = 0;
	}
	~Stack()
	{
		cout << "~Stack()" << endl;
		free(_a);
		_a = nullptr;
		_top = _capacity = 0;
	}
private:
	STDataType* _a;
	size_t _capacity;
	size_t _top;
};
// 两个Stack实现队列
class MyQueue
{
public:
	//编译器默认⽣成MyQueue的析构函数调⽤了Stack的析构，释放的Stack内部的资源
	// 显⽰写析构，也会⾃动调⽤Stack的析构
	/*~MyQueue()
	{}*/
private:
	Stack pushst;
	Stack popst;
};
int main()
{
	Stack st;
	MyQueue mq;
	return 0;
}


#include<iostream>
using namespace std;
// ⽤最新加了构造和析构的C++版本Stack实现
bool isValid(const char* s) {
	Stack st;
	while (*s)
	{
		if (*s == '[' || *s == '(' || *s == '{')
		{
			st.Push(*s);
		}
		else
		{
			// 右括号⽐左括号多，数量匹配问题
			if (st.Empty())
			{
				return false;
			}
			// 栈⾥⾯取左括号
			char top = st.Top();
			st.Pop();
		 // 顺序不匹配
				if ((*s == ']' && top != '[')
					|| (*s == '}' && top != '{')
					|| (*s == ')' && top != '('))
				{
					return false;
				}
		}
		++s;
	}
	// 栈为空，返回真，说明数量都匹配 左括号多，右括号少匹配问题
	return st.Empty();
}
// ⽤之前C版本Stack实现
bool isValid(const char* s) {
	ST st;
	STInit(&st);
	while (*s)
	{
		// 左括号⼊栈
		if (*s == '(' || *s == '[' || *s == '{')
		{
			STPush(&st, *s);
		}
		else // 右括号取栈顶左括号尝试匹配
		{
			if (STEmpty(&st))
			{
				STDestroy(&st);
				return false;
			}
			char top = STTop(&st);
			STPop(&st);
			// 不匹配
			if ((top == '(' && *s != ')')
				|| (top == '{' && *s != '}')
				|| (top == '[' && *s != ']'))
			{
				STDestroy(&st);
				return false;
			}
		}
		++s;
	}
	// 栈不为空，说明左括号⽐右括号多，数量不匹配
	bool ret = STEmpty(&st);
	STDestroy(&st);
	return ret;
}
int main()
{
	cout << isValid("[()][]") << endl;
	cout << isValid("[(])[]") << endl;
	return 0;
}
